#include <cmath>
#include <cstddef>
#include <functional>
#include <iostream>
#include <vector>
using namespace std;

namespace old
{

template<class K>
struct hash
{
    size_t operator()(const K& key)
    {
        return key;
    }
};

template<>
struct hash<string>
{
    size_t operator()(const string& s)
    {
        size_t n = 0;
        for (auto c : s) n = n * 131 + c;
        return n;
    }
};

template<class K>
struct equal_to
{
    bool operator()(const K& k1, const K& k2)
    {
        return k1 == k2;
    }
};

template<class K, class V>
struct hash_node
{
    pair<K, V> _kv;
    hash_node<K, V>* _next;

    hash_node<K, V>(const pair<K, V>& kv) : _kv(kv), _next(nullptr)
    {}
};

template<class K, class V, class Hash = hash<K>, class Pred = equal_to<K>>
class hash_table
{
public:
    typedef hash_node<K, V> node;

public:
    bool insert(const pair<K, V>& kv)
    {
        if (find(kv.first))
            return false;

        if (_table.empty() || _table.size() == _size)
        {
            size_t new_size = _table.empty() ? 10 : _table.size() * 2;
            vector<node*> new_table(new_size);

            for (auto& cur : _table)
            {
                while (cur)
                {
                    size_t hashi =_hash(cur->_kv.first) % new_table.size();
                    node* next = cur->_next;

                    cur->_next = new_table[hashi];
                    new_table[hashi] = cur;

                    cur = next;
                }
            }

            _table.swap(new_table);
        }

        size_t hashi = _hash(kv.first) % _table.size();
        node* new_node = new node(kv);

        new_node->_next = _table[hashi];
        _table[hashi] = new_node;
        ++_size;

        return true;
    }

    node* find(const K& key)
    {
        if (_table.empty())
            return nullptr;

        size_t hashi = _hash(key) % _table.size();
        node* cur = _table[hashi];

        while (cur)
        {
            if (_pred(cur->_kv.first, key))
                return cur;

            cur = cur->_next;
        }

        return nullptr;
    }

    bool erase(const K& key)
    {
        if (_table.empty())
            return false;

        size_t hashi = _hash(key) % _table.size();
        node* cur = _table[hashi];
        node* prev = nullptr;

        while (cur)
        {
            if (_pred(cur->_kv.first, key))
            {
                if (!prev)
                {
                    _table[hashi] = cur->_next;
                }
                else
                {
                    prev->_next = cur->_next;
                }
                delete cur;
                return true;
            }

            prev = cur;
            cur = cur->_next;
        }
        return false;
    }

private:
    vector<node*> _table;
    size_t _size = 0;

    Hash _hash;
    Pred _pred;
};

void test_hash_1()
{
    hash_table<int, int> h1;
    hash_table<string, string> h2;

    h2.insert(make_pair("sort", "paixu"));
    h2.insert(make_pair("left", "zuobian"));
    h2.insert(make_pair("right", "youbian"));
}

void test_hash_2()
{
    int a[] = {3, 33, 2, 13, 5, 13, 12, 1002, 19, 9, 22, 44, 81, 53};
    old::hash_table<int, int> hash;
    for (auto e : a)
    {
        hash.insert({e, e});
    }

    hash.erase(1002);
    hash.erase(22);
    hash.erase(2);
}

}